//https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
package codeRandomThoughts.InterviewTest0207链表相交;

import codeRandomThoughts.utils.ListNode;

//二刷
public class Solution2 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //首先遍历求A和B的长度
        int lengthA = 0;
        int lengthB = 0;
        ListNode currA = headA;
        ListNode currB = headB;
        while (currA!=null){
            lengthA++;
            currA=currA.next;
        }
        while (currB!=null){
            lengthB++;
            currB=currB.next;
        }
        int diff = Math.abs(lengthA - lengthB);
        //让B为较长的那个
        if (lengthA>lengthB){
            ListNode tmp = headB;
            headB = headA;
            headA= tmp;
        }
        currA = headA;
        currB = headB;
        //让B先走diff步
        for (int i = 0; i < diff; i++) {
            currB=currB.next;
        }

        //A和B一起走,遇到第一个相同节点就break
        while (currA!=null&&currB!=null){
            if (currA==currB){
                return currA;
            }
            currA=currA.next;
            currB=currB.next;
        }
        return null;
    }
}
